package com.test.demo;

import java.util.Arrays;

/**
 * Created by jl on 2020/7/3
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] a = {10, 3, 2, 9, 5, 4, 6};
        doQuickSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    private static void doQuickSort(int[] a, int start, int end) {
        if (start >= end) {
            return;
        }
        int kIndex = start;
        for (int i = start + 1; i <= end; i++) {
            if (a[kIndex] > a[i]) {
                move2Left(a, kIndex++, i);
            }
        }
        doQuickSort(a, start, kIndex - 1);
        doQuickSort(a, kIndex + 1, end);
    }

    private static void move2Left(int[] a, int kIndex, int i) {
        int tmp = a[i];
        System.arraycopy(a, kIndex, a, kIndex + 1, i - kIndex);
        a[kIndex] = tmp;
    }
}
